# 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
#
#  示例 1:
# 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
# 输出：6
# 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
#
#
#  示例 2：
# 输入：height = [4,2,0,3,2,5]
# 输出：9
import math
from typing import List


class Rect:
    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height


class Solution:
    """
            单调栈
            一横条一横条能接住的雨水进行累加
            优化思路：单调栈
                维护的是一个Rect.height 单调递减的栈（栈底到栈顶方向单调递减），当单调递减栈的单调性被破坏的时候，
                说明这根柱子可以挡住之前的水，栈顶（最低的柱子）能留住的雨水以栈顶为高度的横条雨水就确定了
            :param heights:
            :return:
            """

    def trap(self, heights: List[int]) -> int:
        sigleStack, res = [], 0
        for h in heights:
            accumulatedWidth = 0
            # 栈顶存储的高度 <= 当前的高度的时候，单调性（单调递增）被破坏，也就确定了当前高度水流的扩展范围
            # 此时需要计算一下这个高度能接住的横条的雨水的面积，并累计答案
            while len(sigleStack) and sigleStack[-1].height <= h:
                tmpRect = sigleStack.pop()
                accumulatedWidth += tmpRect.width
                bottom = tmpRect.height
                if not len(sigleStack):  # 水全部从左边流走了
                    continue
                up = min(h, sigleStack[-1].height)  # 以 bottom 为底的横块水， 最高可以到 up
                res += accumulatedWidth * (up - bottom)  # 累加答案
            sigleStack.append(Rect(width=accumulatedWidth + 1, height=h))
        return res


if __name__ == '__main__':
    heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    heights = [4, 2, 0, 3, 2, 5]
    print(Solution().trap(heights))
